A discrete artificial bee colony algorithm for the multi-objective flexible job-shop scheduling problem with maintenance activities

This paper presents a novel discrete artificial bee colony (DABC) algorithm for solving the multi-objective flexible job shop scheduling problem with maintenance activities. Performance criteria considered are the maximum completion time so called makespan, the total workload of machines and the workload of the critical machine. Unlike the original ABC algorithm, the proposed DABC algorithm presents a unique solution representation where a food source is represented by two discrete vectors and tabu search (TS) is applied to each food source to generate neighboring food sources for the employed bees, onlooker bees, and scout bees. An efficient initialization scheme is introduced to construct the initial population with a certain level of quality and diversity. A self-adaptive strategy is adopted to enable the DABC algorithm with learning ability for producing neighboring solutions in different promising regions whereas an external Pareto archive set is designed to record the non-dominated solutions found so far. Furthermore, a novel decoding method is also presented to tackle maintenance activities in schedules generated. The proposed DABC algorithm is tested on a set of the well-known benchmark instances from the existing literature. Through a detailed analysis of experimental results, the highly effective and efficient performance of the proposed DABC algorithm is shown against the best performing algorithms from the literature.     

Frequency optimization in public transportation systems: Formulation and metaheuristic approach

We study the transit frequency optimization problem, which aims to determine the time interval between subsequent buses for a set of public transportation lines given by their itineraries, i.e., sequences of stops and street sections. The solution should satisfy a given origin–destination demand and a constraint on the available fleet of buses. We propose a new mixed integer linear programming (MILP) formulation for an already existing model, originally formulated as a nonlinear bilevel one. The proposed formulation is able to solve to optimality real small-sized instances of the problem using MILP techniques. For solving larger instances we propose a metaheuristic which accuracy is estimated by comparing against exact results (when possible). Both exact and approximated approaches are tested by using existing cases, including a real one related to a small-city which public transportation system comprises 13 lines. The magnitude of the improvement of that system obtained by applying the proposed methodologies, is comparable with the improvements reported in the literature, related to other real systems. Also, we investigate the applicability of the metaheuristic to a larger-sized real case, comprising more than 130 lines.     

Simulated annealing and tabu search approaches for the Corridor Allocation Problem

In the Corridor Allocation Problem, we are given n facilities to be arranged along a corridor. The arrangements on either side of the corridor should start from a common point on the left end of the corridor. In addition, no space is allowed between two adjacent facilities. The problem is motivated by applications such as the arrangement of rooms in office buildings, hospitals, shopping centers or schools. Tabu search and simulated annealing algorithms are presented to minimize the sum of weighted distances between every pair of facilities. The algorithms are evaluated on several instances of different sizes either randomly generated or available in the literature. Both algorithms reached the optimal (when available) or best-known solutions of the instances with n ? 30. For larger instances with size 42 ? n ? 70, the simulated annealing implementation obtained smaller objective values, while requiring a smaller number of function evaluations.     

Accelerating CFD–DEM simulation of processes with wide particle size distributions

Size-reduction systems have been extensively used in industry for many years. Nevertheless, reliable engineering tools to be used to predict the comminution of particles are scarce. Computational fluid dynamics (CFD)–discrete element model (DEM) numerical simulation may be used to predict such a complex phenomenon and therefore establish a proper design and optimization model for comminution systems. They may also be used to predict attrition in systems where particle attrition is significant. Therefore, empirical comminution functions (which are applicable for any attrition/comminution process), such as: strength distribution, selection, equivalence, breakage, and fatigue, have been integrated into the three-dimensional CFD–DEM simulation tool. The main drawback of such a design tool is the long computational time required owing to the large number of particles and the minute time-step required to maintain a steady solution while simulating the flow of particulate materials with very fine particles.The present study developed several methods to accelerate CFD–DEM simulations: reducing the number of operations carried out at the single-particle level, constructing a DEM grid detached from the CFD grid enabling a no binary search, generating a sub-grid within the DEM grid to enable a no binary search for fine particles, and increasing the computational time-step and eliminating the finest particles in the simulation while still tracking their contribution to the process.The total speedup of the simulation process without the elimination of the finest particles was a factor of about 17. The elimination of the finest particles gave additional speedup of a factor of at least 18. Therefore, the simulation of a grinding process can run at least 300 times faster than the conventional method in which a standard no binary search is employed and the smallest particles are tracked.     

Precise and global identification of phospholipid molecular species by an Orbitrap mass spectrometer and automated search engine Lipid Search

In the present research, we have established a new lipidomics approach for the comprehensive and precise identification of molecular species in a crude lipid mixture using a LTQ Orbitrap mass spectrometer (MS) and reverse-phase liquid chromatography (RPLC) combination with our newly developed lipid search engine “Lipid Search”. LTQ Orbitrap provides high mass accuracy MS spectra by Fourier-transform (FT) mass spectrometer mode and can perform rapid MSⁿ by ion trap (IT) mass spectrometer mode. In this study, the negative ion mode was selected to detect fragment ions from phospholipids, such as fatty acid anions, by MS2 or MS3. We selected the specific detection approach by neutral loss survey-dependent MS3, for the identification of molecular species of phosphatidylcholine, sphingomyelin and phosphatidylserine. Identification of molecular species was performed by using both the high mass accuracy of the mass spectrometric data obtained from FT mode and structural data obtained from fragments in IT mode. Some alkylacyl and alkenylacyl species have the same m/z value as molecular-related ions and fragment ions, thus, direct acid hydrolysis analysis was performed to identify alkylacyl and alkenylacyl species, and then the RPLC–LTQ Orbitrap method was applied. As a result, 290 species from mouse liver and 248 species from mouse brain were identified within six different classes of phospholipid, only those in manually detected and confirmed. Most of all manually detected mass peaks were also automatically detected by “Lipid Search”. Adding to differences in molecular species in different classes of phospholipids, many characteristic differences in molecular species were detected in mouse liver and brain. More variable number of saturated and monounsaturated fatty acid-containing molecular species were detected in mouse brain than liver.     

On an M (X)/G/1 Retrial System with Two Types of Search of Customers from the Orbit

Single server retrial queueing models in which customers arrive according to a batch Poisson process are considered here. An arriving batch, finding the server busy, enters an orbit. Otherwise, one customer from the arriving batch enters for service immediately while the rest join the orbit. The customers from the orbit (the orbital customers) try to reach the server subsequently with the inter-retrial times exponentially distributed. Additionally, at each service completion epoch, two different search mechanisms, that is, type I and type II search, to bring the orbital customers by the system to service, are switched on. Thus, when the server is idle, a competition takes place among primary customers, customers who come by retrial and by two types of searches. The type I search selects a single customer whereas the type II search considers a batch of customers from the orbit. Depending on the maximum size of the batch being considered for service by a type II search, two cases are addressed here. In the first case, no restriction on batch size is assumed, whereas in the second case, maximum size of the batch is restricted to a pre-assigned value. We call the resulting models as model 1 and model 2 respectively. In all service modes other than type II search, only a single customer is qualified for service. Service times of the four types of customers, namely, primary, repeated, and those who come by two types of searches are arbitrarily distributed (with different distributions which are independent of each other). Steady state analysis is performed and stability conditions are established. A control problem for model 2 is considered and numerical illustrations are provided.     

Hierarchical approach for survivable network design

A central design challenge facing network planners is how to select a cost-effective network configuration that can provide uninterrupted service despite edge failures. In this paper, we study the Survivable Network Design (SND) problem, a core model underlying the design of such resilient networks that incorporates complex cost and connectivity trade-offs. Given an undirected graph with specified edge costs and (integer) connectivity requirements between pairs of nodes, the SND problem seeks the minimum cost set of edges that interconnects each node pair with at least as many edge-disjoint paths as the connectivity requirement of the nodes. We develop a hierarchical approach for solving the problem that integrates ideas from decomposition, tabu search, randomization, and optimization. The approach decomposes the SND problem into two subproblems, Backbone design and Access design, and uses an iterative multi-stage method for solving the SND problem in a hierarchical fashion. Since both subproblems are NP-hard, we develop effective optimization-based tabu search strategies that balance intensification and diversification to identify near-optimal solutions. To initiate this method, we develop two heuristic procedures that can yield good starting points. We test the combined approach on large-scale SND instances, and empirically assess the quality of the solutions vis-à-vis optimal values or lower bounds. On average, our hierarchical solution approach generates solutions within 2.7% of optimality even for very large problems (that cannot be solved using exact methods), and our results demonstrate that the performance of the method is robust for a variety of problems with different size and connectivity characteristics.     

Static search games played over graphs and general metric spaces

We define a general game which forms a basis for modelling situations of static search and concealment over regions with spatial structure. The game involves two players, the searching player and the concealing player, and is played over a metric space. Each player simultaneously chooses to deploy at a point in the space; the searching player receiving a payoff of 1 if his opponent lies within a predetermined radius r of his position, the concealing player receiving a payoff of 1 otherwise. The concepts of dominance and equivalence of strategies are examined in the context of this game, before focusing on the more specific case of the game played over a graph. Methods are presented to simplify the analysis of such games, both by means of the iterated elimination of dominated strategies and through consideration of automorphisms of the graph. Lower and upper bounds on the value of the game are presented and optimal mixed strategies are calculated for games played over a particular family of graphs.     

带约束条件的停车场启发式停车诱导算法

随着城市化进程的推进,市区停车难严重制约交通的发展。针对停车场使用效率低下问题,分析了影响车位选择的各种因素,提出带有约束条件的泊车诱导算法,通过划分场内小区保证车辆在空间均衡分布,以最短行驶路径/时间和停车难度两项指标衡量道路权重,使用改进的启发式A*搜索算法计算最佳车位。仿真结果证明方法合理可行,在时间和效率上有所节省,所选的最佳车位更符合实际情况。     

GHS + LEM: Global-best Harmony Search using learnable evolution models

This paper presents a new optimization algorithm called GHS + LEM, which is based on the Global-best Harmony Search algorithm (GHS) and techniques from the learnable evolution models (LEM) to improve convergence and accuracy of the algorithm. The performance of the algorithm is evaluated with fifteen optimization functions commonly used by the optimization community. In addition, the results obtained are compared against the original Harmony Search algorithm, the Improved Harmony Search algorithm and the Global-best Harmony Search algorithm. The assessment shows that the proposed algorithm (GHS + LEM) improves the accuracy of the results obtained in relation to the other options, producing better results in most situations, but more specifically in problems with high dimensionality, where it offers a faster convergence with fewer iterations.